public class Test {
    //JZ10 斐波那契数列
    public int Fibonacci(int n) {
        if(n <= 2){
            return 1;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
    //JZ11 旋转数组的最小数字
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //若中间值大于最右边，说明目标在中间值右边
            if(array[mid] > array[right]){
                left = mid + 1;
            }
            //一下严防 1 1 1 0 1
            else if(array[mid] == array[right]){
                right--;
            }
            //不在右边就在左边
            else{
                right = mid;
            }
        }
        return array[left];
    }
    //JZ17 打印从1到最大的n位数
    public int[] printNumbers (int n) {
        // write code here
        int end = (int)Math.pow(10,n);
        int[] array = new int[end - 1];
        for(int i = 1; i < end; i++){
            array[i - 1] = i;
        }
        return array;
    }
    //JZ18 删除链表的节点
    public ListNode deleteNode (ListNode head, int val) {
        // write code here
        ListNode cur = head;
        ListNode prev = null;
        while(cur != null){
            //找到被删除的结点
            if(cur.val == val){
                //待删除的结点为头结点
                if(cur == head){
                    head = head.next;
                    break;
                }
                //待删除结点是尾结点
                else if(cur.next == null){
                    prev.next = null;
                    break;
                }
                //待删除的结点在中间
                else{
                    prev.next = cur.next;
                    break;
                }
            }
            prev = cur;
            cur = cur.next;
        }
        return head;
    }
    //JZ21 调整数组顺序使奇数位于偶数前面(一)双指针解法
    public int[] reOrderArray (int[] array) {
        // write code here
        //先遍历一遍数组，统计奇数的个数，最后放入新数组(满足时间复杂度O(n))
        int len = array.length;
        int[] elem = new int[len];
        //统计奇数个数
        int count = 0;
        for(int i = 0; i < len; i++){
            if(array[i] % 2 != 0){
                count++;
            }
        }
        int left = 0;
        int right = count;
        for(int i = 0; i < len; i++){
            if(array[i] % 2 != 0){
                elem[left++] = array[i];
            }else{
                elem[right++] = array[i];
            }
        }
        return elem;
    }
    //JZ81 调整数组顺序使奇数位于偶数前面(二)
    public int[] reOrderArray2 (int[] array) {
        // write code here
        //新数组版(时间复杂度依旧是O(n))
        int len = array.length;
        int[] elem = new int[len];
        //新数组的下标
        int index = 0;
        //移入奇数
        for(int i = 0; i < len; i++){
            if(array[i] % 2 != 0){
                elem[index++] = array[i];
            }
        }
        for(int i = 0; i < len; i++){
            if(array[i] % 2 == 0){
                elem[index++] = array[i];
            }
        }
        return elem;
    }
}
